package coursera.assignments;

/**
 * @author sachintakkar
 * 
 */
public class AlgorithmsProblem2QuickSort {

	/**
	 * Testing quick sort method.
	 * 
	 * @param args
	 */

	static int totalComparisons = 0;

	public static void main(String[] args) {
		AlgorithmsProblem2QuickSort qs = new AlgorithmsProblem2QuickSort();
		int [] inputArray1 = getinputArray1();
		int [] inputArray2 = getinputArray2();
		int [] inputArray = new int[10000];
		int j=0;
		for (int x=0;x<=inputArray1.length-1 ;x++){
			inputArray[j] = inputArray1[x];
			j++;
		}
		for (int y=0;y<=inputArray2.length-1 ;y++){
			inputArray[j] = inputArray2[y];
			j++;
		}
		
		qs.sort(inputArray, 0, inputArray.length-1);
		System.out.println("Total Comparisons" + totalComparisons);
		for (int i = 0; i < inputArray.length; i++)
			System.out.println(" " + inputArray[i]);
	}

	private static int[] getinputArray1() {
		return new int[] {2148,9058,7742,3153,6324,609,7628,5469,7017,504,4092,1582,9572,1542,5697,2081,4218,3130,7923,9595,6558,3859,9832,3062,6788,7578,7432,479,8439,9079,7173,2667,2770,2655,972,4264,2014,3171,4715,345,4388,3816,8887,3915,3490,2327,123,4596,4307,8737,4007,6798,6551,1627,1190,4984,2480,3404,2027,4778,2951,2795,5002,8121,8910,9593,5254,448,6237,5565,1816,392,8143,9310,9293,3138,4869,6756,872,6183,3517,3513,1676,5498,9172,5739,6108,7538,7671,5780,8666,540,9771,6837,9341,1590,5689,1605,1103,5859,1622,4371,3113,488,6676,6020,2630,6541,6893,6729,4506,3230,2290,72,1976,8259,1373,9962,782,4427,6349,9619,4456,7750,41,8687,5506,2128,578,8001,4493,9107,746,2639,1456,1361,2841,3198,6344,1450,3346,6221,4816,3800,9975,8075,2400,1353,2282,147,2821,497,9028,9448,3574,2209,138,8201,2331,3895,7803,2406,9949,1349,965,1320,8836,9562,5753,1039,2348,2184,8212,4909,3025,1690,6117,7318,6478,768,4551,1054,7000,97,6868,5870,7601,6257,5461,8029,7797,1149,1216,4359,3524,556,1451,8976,1988,7949,6444,3787,8116,2381,1465,971,2917,5502,6225,3482,2078,3013,4993,5924,8444,1271,1032,1708,5366,3841,3112,9234,4156,1849,8718,396,4231,2517,3773,4088,1006,2623,7534,7113,2218,1175,1879,3188,7698,4226,2644,2625,8237,8644,3649,7304,8242,800,7335,4589,1619,1996,699,7991,4889,6241,5444,8466,7658,9880,378,2112,2831,3737,988,2619,3354,6426,4602,6058,1068,9614,6235,2049,7151,9038,232,5336,6988,6467,306,480,716,4800,9048,7423,294,8595,8055,8542,7516,1398,490,219,2820,4777,2030,7729,5005,8544,597,8790,740,2443,5217,6178,2338,8176,8320,6521,6597,5186,6604,9467,2598,6898,3274,8254,947,1178,8770,3910,8314,543,605,9893,4699,443,6569,1723,2920,4665,174,9769,1672,9560,3470,9641,5199,3395,6461,9204,2930,7379,7034,4229,9634,15,2631,8815,4609,7011,6664,5392,2158,6190,1782,460,9991,30,5269,2117,8819,7039,5766,960,4608,6211,6389,4584,6448,3763,5126,1319,4821,1207,5896,2262,3492,5830,9260,2905,5189,2653,1488,9827,6167,3439,5841,1078,331,1579,469,2608,5944,4681,4751,9882,1044,1788,8551,3628,178,213,4961,6999,7221,3725,9162,3196,5309,6545,4337,7149,39,3699,5314,3252,1601,2779,5849,6739,249,2665,1537,2811,1107,5272,9872,2704,6671,1472,5059,1518,2408,6762,2891,6764,6628,680,3313,1128,6679,215,545,7806,6754,1387,9125,3868,2512,2903,4625,4873,9514,1731,4100,7848,6842,1281,1759,1242,4735,758,3412,7169,1918,7385,2429,9175,2017,7986,1887,2875,1233,4217,6834,4573,3047,6445,5302,4319,2547,9452,4881,7093,3518,4549,9131,4502,26,1136,1847,3503,322,6519,9471,8330,2224,7585,5823,5408,541,1377,4098,1193,2149,6456,4795,6256,5448,776,5439,1135,6316,4076,2187,1058,4779,2473,678,5891,4119,4623,8299,7720,9329,9728,1921,1389,1637,8375,5255,5304,8612,1978,6446,744,7101,7679,3478,9182,547,316,3445,4344,1140,661,6878,4730,2452,3948,8152,7124,4424,2713,8580,5514,8369,2201,8511,4300,5803,1449,7692,3968,9077,2036,2718,399,8537,9494,3276,9996,4387,8336,1625,2659,1402,2086,9648,995,7888,1548,8994,4070,7488,8256,8089,3186,5497,5993,1118,1363,6479,4952,6704,4951,4247,3593,3071,3462,9297,4164,1368,2346,6223,5229,976,3356,4382,9900,5277,5617,3145,784,4981,9009,6102,8452,1008,3136,2468,2664,32,6260,6610,7298,7205,9824,2107,5815,9284,5718,6840,2390,775,3760,3132,6951,9088,5072,8448,6148,3625,4162,2997,1926,1231,387,5361,2191,2758,9788,4946,4534,2033,4992,5359,4452,1240,2138,5033,8740,9165,4570,1784,6404,2065,197,9480,821,4774,1241,8313,6210,2032,2818,9313,6744,3265,2793,8915,2798,1754,5781,7856,2493,1777,5943,5598,7225,2295,2744,2956,3330,4671,5666,5212,3268,2504,8541,4910,6797,2435,7187,4958,3197,8985,4540,1197,6517,3911,9995,742,5382,4649,7640,3681,1003,96,3597,7551,4011,3359,1757,485,4662,3319,4685,3589,2575,1753,4358,5619,446,6051,2159,4223,905,4302,2879,2425,6715,3087,5083,4651,5432,3541,3074,2721,5460,3928,3321,2293,6325,1191,1528,5055,1736,5036,5938,5636,7773,8699,2781,2377,4913,6458,906,7464,5286,2090,4421,2986,5262,5913,7073,7240,8119,9983,2726,6925,2279,5804,9974,1196,4442,2642,1279,4274,4853,5291,314,7344,7211,447,6931,7984,9431,2693,1321,1208,7440,236,8412,3289,6539,7492,5832,2445,2349,3674,7159,4760,863,5791,3692,3599,5980,9374,2012,2061,867,526,1088,1030,5518,4384,1474,3374,2441,3474,2395,2535,3664,5138,7251,3388,2904,2066,7845,3984,2596,8816,4632,3254,7581,1236,4285,8307,9338,1875,2210,7979,2549,7690,3961,4729,2072,6733,8675,4518,5585,7256,1525,7728,6965,5093,512,840,6161,4842,5985,495,1023,1089,2842,9096,1344,986,674,1683,1963,3175,3165,3091,78,4128,7033,2604,8532,272,6680,6928,3426,2140,2689,2858,5296,3587,2075,2500,9524,7376,5118,4024,8565,4395,2966,1544,224,1612,7582,7587,2981,9153,2942,2361,237,2643,1598,3007,4674,4227,6818,544,4360,558,1831,1249,5681,8186,9967,6537,4062,3531,4579,6304,8785,7594,2240,1230,7241,5519,4633,9103,881,6138,1751,1636,5500,4894,2584,70,8869,9535,5409,4950,4455,6899,7487,3565,5251,2485,4677,568,4151,1808,2554,9391,2878,9439,9327,951,9211,1457,5774,9199,1290,7520,6216,6299,820,574,7153,3006,6105,3908,8162,6061,8146,7891,5695,5057,6357,7381,4440,3631,8668,6278,7895,9971,2242,6525,6050,6440,1470,1506,258,9946,6690,2037,1685,7343,2048,3332,2489,2654,9246,6337,3736,8482,6402,3421,6870,7232,4312,6909,4864,7495,2260,5190,8006,7459,8132,4330,3484,5755,4350,2751,2487,4535,2278,3790,4189,4711,5357,2301,8021,2054,2647,9394,4017,6839,1116,5342,8854,1633,626,7126,9808,9298,1057,2043,6165,9397,8378,5295,685,2132,6767,9884,7669,3367,6624,5128,625,9434,1634,570,6027,7506,5836,8434,2264,1292,2057,6749,2447,3546,9713,5253,2824,4547,4135,506,1689,5655,2157,9791,7540,120,8433,132,7710,653,9988,3223,483,9239,3075,8436,4580,6238,3719,4695,8536,4505,5628,6802,1823,885,46,4049,8959,4157,2241,5573,3642,3120,1790,117,2102,5102,3156,6290,846,3502,6935,5490,4318,9976,8117,4832,8945,2164,5452,9274,470,8158,8493,4150,8708,3943,7306,721,8332,3983,4447,8353,1624,9229,1934,5494,8447,6195,4835,2537,9663,9344,2805,528,3278,3922,4639,4339,5434,3569,6627,2816,4103,7112,3133,4947,6605,5763,3488,2946,3781,275,5299,1508,7866,1378,8368,8470,5883,5193,5838,5038,2071,4104,172,4495,2790,3842,8948,8387,2268,2720,6752,3294,3680,8112,8768,1228,9749,5065,6661,1315,1445,2685,2579,3317,1523,3299,7351,1329,7437,4411,3991,5029,959,7360,2249,6970,3444,2234,4425,1889,4257,1955,9040,34,8778,5825,6629,7852,315,6600,5437,9848,4201,7048,8228,3340,5608,228,7491,3857,6469,3078,850,4756,645,7882,2999,2687,1336,2510,4507,149,1863,3017,2872,8009,2455,5976,7429,9438,3584,3676,5267,3675,2047,801,7693,3724,6859,1713,4576,9803,5932,6381,1968,4544,3621,808,357,2716,6670,9814,8110,4846,7568,3212,8701,4822,2375,3889,1370,8339,3955,8128,9138,5583,5989,1444,1828,1201,8707,868,6353,8825,2850,2712,6643,5080,7505,4679,3855,2834,3420,5940,1148,4167,3301,1715,19,362,3261,7415,1698,8845,5204,7779,5837,4386,7302,4924,6656,3249,2463,5593,3757,478,2332,3077,4102,2296,5105,9510,7224,4001,8319,2474,5828,2916,5381,3243,6326,5754,854,5166,2564,1001,8594,5625,5709,9969,3626,3557,8458,4301,4919,1667,7366,3863,5367,7280,3946,500,8187,8863,9312,1055,2591,8641,8949,9544,6129,1501,5319,2582,4539,4280,9661,351,6954,4043,3273,5687,5969,369,7804,7139,4265,8363,7314,8008,3970,7983,2780,5665,3820,8741,2022,9398,2409,244,1461,5910,4594,2648,20,2439,3378,8638,3177,6691,6979,2180,3615,8450,2988,5996,2743,2115,1526,5086,4352,8323,6174,1498,8639,7947,2005,843,5893,4791,5594,8190,7667,3780,9169,9870,5052,2715,1422,240,1635,6950,6420,2139,1460,9579,9386,702,7132,9420,2701,4520,8397,2495,5539,3886,3672,2393,5790,5227,6460,841,5495,4214,4014,4238,4604,1970,3605,364,9551,1254,930,8761,4246,4249,1181,170,7065,74,6187,8950,4237,4198,2207,4854,1892,7834,975,7675,9885,4528,4953,1053,148,5380,3887,704,4515,3588,9080,1739,8852,1785,991,1141,7625,2436,1487,8822,1574,5524,1742,7724,7977,3709,277,7030,4025,505,4706,7489,9091,7726,3425,5616,365,9044,4317,871,7165,1794,3366,1878,9584,5056,5486,2431,5528,2749,3432,5964,2023,9565,9357,3711,6953,5764,3604,9417,4916,8304,6997,2646,5431,4391,474,1740,3637,1383,5761,7477,3184,6499,5044,3473,267,2877,3933,6723,4316,6945,476,7372,9035,2794,9463,2255,3927,3823,5061,8372,7215,2161,1864,1247,6867,7195,6501,7270,3739,6418,2479,3155,226,6721,4906,9583,922,1931,3417,343,3907,2733,3876,1566,5966,4548,4351,3392,6147,5264,5733,7898,2354,4481,8157,4332,4963,8823,2213,3732,2529,1846,777,2789,5638,2370,1018,4286,6003,6496,3891,1992,7367,6336,4292,3396,1293,1592,8107,1567,711,209,2013,5115,207,3987,4994,8311,1203,8588,993,6291,4523,1443,3090,1648,2699,5247,6480,4177,8973,1610,4803,7412,6234,3716,2176,6038,5848,7659,7680,1684,5463,9447,373,833,1530,1335,6769,2077,7092,2459,6375,5710,7192,2835,781,7443,5522,6280,7413,1077,1189,3827,1414,3643,5324,6974,8715,3287,6502,1218,7155,1157,4582,38,5344,6043,3937,2614,7812,4109,9924,9219,4243,7289,56,9701,5081,2656,3250,3723,1938,317,4741,8797,9464,9537,7535,1839,1337,5179,2420,9192,9625,8487,985,2266,509,2318,3963,7051,5586,7567,2628,6244,5351,9826,7966,5225,3044,5802,5310,3717,5406,989,1870,7125,4220,3843,2261,4785,2569,3691,6618,6718,217,1983,1951,8173,633,5273,4041,8010,9690,4075,8445,3634,9465,6214,7849,4650,1485,3845,7013,1767,291,9020,3019,3890,4490,5120,5429,5402,5041,7070,5967,7881,9628,1204,5011,6428,2494,1950,4847,4550,3009,492,7271,3745,7989,33,4366,887,7730,3814,5941,2325,1490,7312,9637,3004,2204,2143,5368,204,3476,7886,510,8961,2141,7975,5656,1806,2522,3931,5427,8141,8118,1183,1328,126,1275,1948,2323,2967,44,1940,6439,5284,3772,1797,2084,2020,168,8125,9864,9090,7591,6917,9790,5250,37,6853,9095,5021,9000,9569,7545,3463,4187,5443,8191,6919,6254,9775,4256,6242,2963,7904,7425,8312,3220,4574,6182,2910,8351,1762,42,2853,8550,4636,3069,9270,8747,7462,5817,5984,6772,1973,2991,5581,7189,3862,7352,6696,7044,2122,3232,7696,6328,617,6929,8241,8280,4619,3094,9245,1139,269,8103,5570,107,1093,4879,7434,9135,5387,9918,3679,5,171,2690,1783,9896,106,8572,9883,9295,8510,9134,958,6573,2193,165,3536,3521,5615,6774,3382,6827,5526,1348,9212,2108,3735,3467,6229,5963,1035,9202,8113,1009,2006,7315,5025,3552,5918,8923,3111,3070,2339,9363,2871,7216,796,902,9871,8385,1393,5023,9994,5043,2691,2137,3979,3337,7076,6307,6832,1629,4380,8667,6047,2804,5887,2330,9325,7633,2336,5735,7926,3256,2652,3529,4450,4348,382,4026,5185,644,2104,2235,8273,8415,2490,1827,5882,9879,5782,1028,8215,3339,1091,1385,5723,7009,3598,7579,3892,1504,3349,5730,9968,2245,4725,9487,1420,429,299,9507,1705,9047,8844,4390,5390,3996,6199,2607,2272,8440,7553,1276,4833,222,3452,4965,1538,6615,7733,3755,9738,6286,6350,8601,145,3617,4600,5595,1296,9951,4841,6391,8877,1752,9407,8268,907,6589,9014,753,6532,828,5612,6181,5355,9620,1929,6626,952,129,2205,1221,425,2456,5198,5341,3960,3303,5888,2428,3110,2285,7007,379,3195,655,3926,459,4978,6033,2746,2446,4000,8486,9903,4663,5510,3533,2303,8824,6032,6144,4485,4441,4858,1159,4477,1562,227,5512,2637,670,2202,4484,2197,4597,9586,7901,4519,372,2935,7410,2475,3491,9607,7523,1491,3837,5827,7707,8291,2516,5388,6506,7267,8389,4023,1789,9889,2788,4383,9557,8026,5258,6513,3768,1392,3247,9474,6944,6978,1600,7026,4199,4446,2662,3460,6295,264,6912,450,9866,3456,9539,1842,9635,7751,8904,3730,390,1015,8480,1814,2709,616,3211,3233,8222,7411,5719,2861,6992,7963,4416,4463,1662,2791,729,8722,9086,7472,2606,6984,1489,977,518,8097,5851,6811,4080,875,2786,7778,4546,5990,6959,3661,9760,1905,3263,9731,6146,2696,6986,5211,6675,3322,8975,4997,9907,8207,6983,8875,1080,3812,8272,3400,7570,2461,632,9377,5466,696,4155,6815,5987,5507,3160,6179,1311,441,7544,1262,4526,2379,6262,599,7760,355,7338,2188,7576,5880,2533,7783,1599,499,9643,9689,6103,4675,1725,933,7546,5988,4278,7170,88,6001,7285,4069,9384,2555,5332,9548,2678,3362,2552,8590,2530,1721,622,6359,799,5018,6509,2039,2995,3255,388,8013,7745,9208,5760,2777,3331,5897,4717,9742,4096,471,755,7393,4208,3464,6939,9110,7190,5478,2265,4850,5939,2828,9102,3700,2836,5509,8710,7607,2099,8575,3712,9499,1429,4073,5339,4050,7615,5752,6063,7833,2351,1051,295,1417,4115,1985,1509,8015,3466,1873,5112,4934,9410,1571,8046,8170,2833,1238,8210,2806,3898,5422,35,3206,7347,7605,6584,4959,2945,8465,367,8398,4028,3076,3144,2004,8799,2548,9673,710,3085,6891,9797,2886,4402,1481,739,2896,6587,2471,2418,5623,4902,3534,8714,1161,9799,8315,7533,7001,3835,6800,2745,6141,1776,9018,4309,3582,4890,2560,8043,5232,9005,6995,1516,5124,3344,8563,5843,6269,1455,8022,5895,9366,1224,5861,3162,6799,7138,8585,717,2380,1586,5177,7475,7715,6955,4211,4970,5858,9953,8101,3795,2531,849,914,8871,5134,1274,7371,6968,4936,7528,6397,6080,5160,4251,5236,3207,7040,9154,5677,6869,1124,8988,5945,7272,730,3627,3103,3606,5821,9874,3411,5414,9262,2985,4882,5596,3405,6814,5078,7713,2367,822,114,1616,4737,1406,2941,7046,6365,757,8777,4692,4375,6272,4680,8609,4666,4982,4875,9392,4877,1421,7766,8547,8366,7118,8729,9381,9008,7617,9806,371,1628,7201,8531,4108,5108,9809,4793,5067,2070,9334,4618,7810,7943,6089,9580,7028,3656,1395,7414,5679,9657,2087,2422,1375,3520,7102,5852,6677,6481,5047,2586,1394,3718,6505,6961,6036,7718,8004,7584,4669,8229,5459,2962,2925,8065,1312,1728,7992,5959,144,6535,196,2067,7106,90,2990,4823,6239,4469,8160,1647,8442,3353,1826,4403,5242,647,9955,6118,323,1925,4311,6864,3429,6383,3431,927,7863,7231,105,9793,2483,6606,856,4912,5771,3398,3671,537,326,7777,7748,8446,278,1867,7456,2545,8517,1259,1341,230,7145,1288,5533,7754,6078,9481,1898,1355,2412,7723,4754,2503,803,6472,2298,7357,9787,8512,3334,1903,9072,484,1027,3514,8264,877,5240,8846,1176,8277,9688,8245,9597,4990,8516,4766,64,2267,4941,4716,8831,2668,6143,8897,2178,4378,2803,2101,7794,5685,861,5451,8279,45,8159,8377,5445,8750,790,8453,166,7394,2940,1475,948,28,6012,5028,8390,7337,1737,9754,6297,8649,6093,9963,6757,4215,750,6586,8943,7784,6516,7972,3066,8813,4200,7436,7738,3702,3180,3267,8967,8748,7433,2722,4401,6282,7952,1384,3856,6880,1533,5349,2895,1258,29,2767,8765,3424,1019,8990,3537,3386,5692,8751,3486,6110,7756,6655,7406,4688,6683,6993,9416,6287,6500,1076,1650,8909,119,4475,7143,3080,7890,1741,5311,4112,5661,4880,4979,2155,5265,847,9538,4614,2725,9702,6303,7604,2570,8192,5741,4957,1219,5241,3020,5578,5000,2538,424,223,6436,765,2901,9998,8643,5024,1786,9977,5111,8736,2294,7678,931,5643,1206,1142,7408,8693,6889,4219,1989,445,3953,1099,997,6433,5136,9926,8839,3183,2676,2183,3547,6662,5298,6170,1087,8496,433,5879,7047,3271,6441,6086,5811,4093,8694,7239,2867,352,9649,4182,9034,8209,6669,4510,6688,6085,1520,7638,4939,637,3022,5819,8136,1137,6462,5454,4553,6804,3789,2773,5869,4749,2343,7887,9876,6825,2453,3608,789,2989,8859,9645,876,3084,1263,1338,1358,3504,1486,8880,4116,8042,1024,4537,4206,6924,7832,5704,7111,7226,7069,336,3194,6861,7142,7946,2256,1882,4147,6271,4149,6640,3174,811,4601,6004,2768,1105,4849,5271,4514,2675,4812,1865,1345,5652,1108,6347,7654,818,4282,1897,4686,1658,9773,3840,4855,4143,8061,208,9919,62,2840,5317,1002,6751,7268,2345,5901,9912,3899,6279,1801,6786,9461,9440,2847,3371,6150,3224,6035,2449,115,6768,2069,8317,3577,9906,3651,3981,6966,3653,1775,4205,4848,4911,7450,9780,1756,3125,6421,6411,6374,3147,6068,5169,4831,2317,1724,6201,8935,4659,7066,4945,4046,8977,3990,7532,7660,4759,911,6557,2015,6205,1565,3485,8310,3199,5818,5401,7454,1085,973,8622,4430,5481,5669,3083,3714,3126,4720,4258,7483,2353,2123,1597,9375,688,6065,8358,6416,9934,3568,1884,7829,5971,956,7308,7362,8774,180,6401,4504,551,6522,4381,3081,2283,1868,700,8283,7599,7389,2627,552,1638,3341,2893,8007,4372,6726,8602,6323,732,6622,2612,8552,9898,715,8617,4476,1572,587,201,8698,3098,2206,7230,248,4661,4263,8502,4428,8219,5769,2322,6906,3560,8746,8856,4710,9084,3666,1426,4884,7291,110,5410,4787,681,3966,7198,2407,1935,9158,5006,8533,6246,3600,5462,9243,5165,4719,2536,2980,1895,3851,1322,2620,884,6056,1144,9403,630,7091,3511,705,7088,9930,5946,391,6289,4817,5559,8100,1071,8474,7210,4876,5549,2610,3342,1906,5010,3097,4834,5654,2383,7510,4306,3058,815,2987,3391,8986,9917,5333,4975,6370,2372,7229,1134,3738,5505,9599,5682,567,2307,5130,406,7064,4512,5798,4738,7821,2953,3865,9066,1550,8742,892,279,8689,2217,6658,9470,2913,7919,2742,23,3905,7384,9505,5233,6503,1910,3235,1881,7269,3316,6059,5994,2969,844,7744,8771,6255,1990,3347,2040,3063,9,9164,1583,7967,5574,7652,8900,5220,4099,3663,5743,4129,3875,9531,8509,9842,5027,3586,3880,3036,7321,5249,2384,4287,6914,3418,9123,5372,4405,7749,4500,4281,122,6905,3323,6872,4967,3170,9489,245,7322,1160,1330,6732,1832,8776,5141,6630,8163,4413,5162,6415,6876,6120,7700,2231,31,7222,4491,3012,8652,8618,9686,2094,4637,2813,9456,7242,6137,3951,2959,738,4558,9441,1732,5077,2275,4731,2869,3300,6438,6267,9429,61,1915,2943,3659,2939,5383,946,8208,9520,809,7087,5671,967,5555,8326,4670,6543,8213,6707,5436,1564,5551,6346,3633,413,3687,4684,157,1033,9564,4781,5742,6258,65,5796,1447,8655,4409,1369,11,2335,1323,6737,6903,917,8610,6609,3509,3472,1130,9526,3241,4839,3613,6854,7801,2166,5060,6639,6697,5379,1223,8012,2389,3884,770,3879,579,1217,3744,4021,198,9845,5483,7493,5090,1939,3535,8417,3925,7634,7175,9488,4458,511,5305,8598,6778,8059,676,8287,9878,9231,8243,4810,6849,4457,3248,4183,8809,1278,360,9592,2649,6684,3828,7068,4545,4192,4185,7903,7128,5348,751,3921,5058,8233,7899,1164,1933,8671,2280,1811,6678,6863,4739,7358,4114,2018,9352,5562,5161,4020,9141,2838,4930,2466,8164,6962,1671,6713,4433,5511,6956,159,9113,8347,5900,9561,3168,2328,7600,2388,1086,6934,7606,7636,6017,8426,7123,3595,4904,2707,4784,3728,3776,7062,5159,8608,5230,4901,2169,1666,9960,1423,3442,7795,9549,9197,4110,2752,7968,3909,2663,1623,8478,1923,8364,6095,4239,3372,8094,8634,284,6533,8150,9970,6153,2363,3100,672,7476,6057,1352,335,1747,7082,1195,3150,7501,3057,2587,6507,2810,9647,9031,3690,5069,9925,3947,5845,941,7147,4016,8587,9379,7244,5425,7969,6442,5046,6107,1036,1037,1042,8873,4072,5155,8631,17,3447,3226,7503,4066,8265,9195,1960,1442,5703,9767,4929,4009,6789,2832,1432,2312,7930,5174,5312,186,8838,4044,8295,9506,2457,1434,6579,5822,9345,4556,6470,5554,3620,5489,2302,3495,4483,5956,1479,7683,5034,1843,6026,8349,402,1773,5756,9817,4722,6451,2650,2763,3630,6782,2594,8914,535,6320,534,8691,3742,9669,6192,4745,8262,3027,2844,7061,943,1944,848,6335,1744,3221,7571,8864,4723,7616,1304,2697,4236,1286,654,5634,2982,4202,3128,7649,6197,1812,1596,8821,466,5981,8092,5395,7917,2839,6293,8384,6497,2823,5050,5340,2374,5127,8329,2076,422,6281,2658,3825,4193,9070,7350,1527,7284,2926,8840,4176,6203,6638,1342,9604,7916,4396,6803,2674,6429,8801,1038,2613,6011,2481,6583,3086,7954,3072,8328,2221,2785,639,7063,8463,6489,259,9305,4640,5706,1410,9610,5464,6039,1380,9676,1439,9316,9013,3107,7518,5644,9830,7097,1553,5419,5488,6657,1356,7378,8549,8286,6779,3262,2884,3073,966,6362,4134,2933,5728,8423,4347,2498,4379,895,6406,6588,1004,7446,8422,5167,281,8189,6971,3826,6642,5885,8063,4204,2827,4843,183,5736,9003,684,4034,4628,6485,6459,6066,1427,5875,690,2581,1205,817,1656,6249,2222,9740,5855,4687,9144,7643,3370,6434,6972,6896,8535,953,6142,7003,6823,918,2385,5779,4555,7031,7542,67,5535,6306,9905,6343,3964,9092,3713,5054,2633,4400,3364,1909,25,3203,3665,4172,8676,1462,3440,356,7740,6540,6578,5731,726,5051,4085,9221,3326,7772,2961,4091,3414,4705,5360,5173,3397,3684,3480,5016,4655,4598,6133,8403,8756,709,6915,5749,5603,7684,4169,337,9215,4262,5303,691,4764,7131,4840,3216,2038,7663,7514,4896,3410,3688,3296,5256,5370,6885,2397,7913,8599,6270,164,5734,4008,9916,894,8592,5807,2996,8054,2031,81,7095,6801,6582,4470,3479,3775,566,8334,6104,9761,1113,6559,6792,393,9063,964,7186,2561,5998,6608,9413,9758,5279,2679,7466,6621,7695,8337,8499,8250,2760,1132,2024,89,1696,8789,2542,8379,5091,1257,754,9281,2915,3580,7976,3139,5246,5183,7416,4734,3722,9444,4503,8410,4464,3867,4126,1360,1248,7228,1165,3448,5321,7286,6547,1534,7858,7945,1171,8341,9418,7598,1558,9496,8574,8848,1411,3974,9497,9940,6045,7974,4905,2698,7727,282,9556,6963,1265,7980,874,8034,5571,7199,9224,8723,8111,1522,6243,9236,1521,53,7257,673,7419,8178,3888,9716,8755,4969,6875,6186,762,4355,8195,6245,6100,9843,7243,5809,3988,7055,9937,8501,128,59,7507,984,5534,6177,9196,8942,2964,3333,2714,1883,4517,4698,3282,9287,82,7855,6313,8781,1280,7592,4324,1651,3042,929,5403,7922,5202,564,5600,1256,792,1701,1244,7323,5902,2692,1855,8648,2344,2756,407,3622,4987,2615,455,3329,5420,4462,2320,3766,4497,9570,3187,6028,1056,1876,9945,6711,2694,5558,7978,5908,8568,7258,1458,9938,5042,3499,5447,1995,4326,8982,7374,2352,3930,3246,9653,4186,3068,1152,7116,2045,4063,2629,5353,2855,3449,3181,3281,3225,8851,163,2304,3403,3231,9659,5607,6185,4592,3849,5306,536,6364,996,1209,6232,1706,9704,9323,2451,6132,5485,4744,2923,6219,8534,7249,8930,6082,2772,4606,6455,1326,8145,2119,4638,1791,256,6114,636,5758,3283,2992,7857,8669,5001,409,7278,5744,6833,9894,9796,8418,6653,9602,6742,69,6483,4809,2085,8978,4973,99,3169,2670,6511,4980,6031,5012,7657,3969,1800,3797,9401,882,4563,3348,4542,1428,1173,1325,8177,8371,7661,1956,6189,4531,1505,8763,3810,6495,6689,5218,8828,3619,9987,2621,9118,4298,1309,7157,3694,6763,9142,5972,332,8582,6727,7665,8686,4938,7018,1270,3002,7609,8725,6013,4920,9227,6646,2759,9252,5053,6276,2518,5147,5750,6074,5079,4678,6941,1466,9240,419,7236,1885,3202,5787,3446,5394,963,193,417,2467,6709,4660,8352,6565,9840,5114,9409,1184,3596,2546,3913,2250,4808,1415,3423,4234,9779,4368,6215,8235,6231,9146,6162,2949,4690,2044,6007,7497,9707,3818,3376,8338,308,8526,4664,9516,6722,9920,5746,9603,829,1214,7227,4612,1317,1665,6777,1584,4210,2334,6218,9703,5732,4700,3999,9585,4465,1513,7705,2394,1709,9340,7631,8032,4196,7774,2062,5098,4838,5991,6964,1750,5660,2088,8204,4991,2929,8866,7024,1966,420,4631,8792,4346,2215,5215,5356,6008,8835,9457,7122,7627,6908,6330,8847,1707,7763,3228,5957,7550,9936,2797,791,6302,350,5794,8407,3707,5435,648,937,9630,8354,4797,7937,8615,8808,9503,5116,4646,5658,3934,4530,6808,2936,6826,7053,1127,2800,2931,5690,92,6616,3101,9333,8983,8270,6784,9263,113,9504,4040,8833,9213,7743,1524,6425,9170,2454,734,7135,7721,2511,1936,4789,4370,7445,8703,9942,5143,195,4888,187,9825,6265,3609,1268,8651,7939,7448,5503,3874,7515,3309,9517,477,7563,6384,8467,9258,3519,3832,3272,5700,7642,9519,5222,4667,261,1467,3727,9225,901,5206,4696,6419,6982,4630,9331};
	}
	
	private static int[] getinputArray2() {
		return new int[] {5407,4089,5385,2848,7865,6927,5846,9588,4999,296,7288,3001,9300,8142,3357,2673,9232,5538,5614,4451,693,8907,4907,3408,1307,4101,6340,8969,436,5109,1815,978,8346,1459,4419,4801,7353,7674,5698,9618,1366,405,8271,4334,4714,5399,3904,3059,6595,6920,7181,5931,1063,9778,7164,9214,1781,9835,8964,5873,2807,4971,919,3427,827,7273,3794,8402,202,787,9479,4259,6475,6090,3561,4053,621,9326,6054,2815,3217,6550,8783,9024,1318,8855,6052,2324,3373,8064,7342,2787,2035,7828,1730,9498,4672,6259,4887,756,6685,5599,5110,6476,4985,1569,6890,6417,7864,8867,2802,8185,5952,5544,1284,1727,7941,7988,4627,1838,7554,5678,6518,2645,3998,8035,9789,2624,9691,7808,3121,9757,1169,804,456,5912,4775,1691,4921,3515,8556,5440,7265,6794,2310,7049,6016,1040,580,7056,1677,9303,6464,4586,6423,4471,5244,199,7172,3176,6493,7331,8938,6240,7736,725,4266,7770,6116,4860,6850,8702,6427,4569,8340,2934,8924,3061,3576,3213,6206,4995,9433,6233,4856,3368,10,6046,4325,320,3251,606,7536,8361,1932,8795,4689,9999,6226,3052,7430,242,3189,8413,9011,3325,7174,5423,3698,7732,8817,7341,4429,6010,6412,9810,5649,9155,3104,432,9042,581,1972,9250,4607,3055,7869,4363,5626,6848,2133,1295,9430,7709,8459,9094,513,5237,6504,2782,6494,2082,4742,2766,9978,1399,2898,3489,743,5430,10000,5543,3311,383,2010,3096,727,860,3906,858,4807,7292,4989,8884,1554,2434,5482,6730,5676,8832,4444,1390,8806,6780,8507,1514,4564,8257,3784,9454,1237,615,2416,2413,6990,2730,590,8886,8490,4983,1484,4956,3471,1798,1115,5630,5686,2616,7160,8393,8321,5516,585,5856,603,5715,6714,7836,6771,3902,604,8296,1965,4084,5151,1014,9768,859,5073,4486,1235,788,3751,6824,3877,2246,4314,3854,6947,3336,5094,6612,2460,5449,9012,1097,2558,584,5201,8225,3399,8464,7441,4002,3686,8606,888,1079,1150,7250,8857,9201,7676,2253,1401,3793,3108,957,2199,8504,6351,6339,2563,9097,3785,2291,2506,6596,8129,1266,6453,6224,5548,8793,1354,7524,7995,340,4437,7305,9616,5768,759,5925,6091,2319,7336,4968,463,7089,7329,3607,7461,8098,7453,6253,5844,324,4232,8288,6860,257,9695,666,4082,6659,7838,5231,8506,3117,9247,9432,2321,6599,5139,7390,5040,1540,5150,5221,4065,1381,5806,1585,4479,3824,2458,5092,5602,4585,4153,6358,7428,737,7290,1211,7781,7277,9251,6647,9388,1780,7827,4728,7438,8842,9292,4974,9226,363,9032,14,7603,1700,8430,7677,8947,3885,1482,1919,2993,6111,2762,752,2523,5450,1333,614,2888,9074,4137,2300,452,5860,7019,6787,6168,4139,5680,2173,7077,2973,6159,9382,2050,472,1539,8126,3545,8805,3669,5606,2109,1546,7512,6698,7368,8811,1886,8036,6603,7021,4087,2028,7016,24,268,5979,8123,992,9139,1156,9039,5765,1155,263,7319,6960,6746,7879,9036,7012,8872,6463,4814,4501,4216,7220,9958,8301,5477,7608,8661,9010,7560,181,7596,6703,7469,5745,6563,6014,4327,3848,85,2950,1287,7630,7722,8993,8800,2971,2846,9159,8775,47,8260,3924,7452,7921,2611,9666,3882,4591,6554,531,2252,9151,2724,5228,8269,9636,50,6508,125,4373,8365,5337,8359,2686,5282,482,5921,1778,7762,1595,7359,2700,9220,4376,6156,1942,9697,4013,9337,1668,6821,221,8294,3555,4769,6725,3583,9484,2812,3166,2273,4891,4828,8632,8830,7490,5031,2736,2060,3227,8688,1692,6886,2860,9280,1817,601,1880,9408,724,3654,7114,9677,7662,7496,5950,4056,9268,5066,2906,4047,7586,5653,6487,9664,2120,8579,1686,9317,1314,8419,98,359,6641,2605,5362,831,6682,6845,9993,7853,7868,9059,9057,1830,310,6946,5157,5426,6124,194,3861,7299,834,5641,862,9502,6382,6841,9002,571,4031,2567,5003,6735,3437,6083,4445,8216,6879,8860,7850,2151,3573,7325,2919,8221,7826,411,4432,517,7825,4752,7583,9612,1560,2539,401,5920,2513,9813,5702,247,2093,1593,4908,6738,921,7925,3829,8558,2865,2001,2008,8451,1499,6062,838,5164,1821,5958,5493,7517,8695,4998,7494,241,457,3035,5154,1980,1464,2277,9126,5536,3266,8607,9148,5180,7465,5194,9078,9746,3662,7997,8220,4727,9540,5580,9609,1679,6888,6884,7397,2737,5713,9156,9443,1073,4367,6366,18,5238,3770,728,3834,442,1896,6069,5364,5015,6847,9120,4033,3746,1975,7522,7893,6296,5552,6308,2577,6134,6158,5358,1119,8663,9798,6207,5564,9815,6892,1813,701,5334,2465,8263,5224,3416,87,5467,6654,9230,5831,3308,5974,5260,634,9100,6361,6592,2074,6024,7672,7482,354,3792,1397,5413,1267,3919,4940,1305,4712,9306,3,8960,3805,9578,225,5397,1174,3030,1959,6407,6753,3575,5530,9027,719,9450,708,4468,6564,4903,4107,3277,428,3512,9747,9383,9984,1277,2059,3450,9235,8168,4770,8645,8124,8896,2769,600,6376,4648,9056,9185,5668,3459,9371,627,9786,6865,2226,9451,6793,218,8140,4141,7622,3771,6087,408,749,468,3115,3167,6528,7771,8027,9055,5121,7873,771,134,2309,7588,9750,3312,669,7467,9571,9859,6266,9083,5672,8367,3527,3994,7156,8899,873,8292,6208,173,4577,5182,9210,5140,9698,4125,9935,9846,3018,583,5627,6491,7032,7811,5611,4827,103,1031,779,6212,4944,2194,8513,1943,3731,7818,898,3893,1016,5727,7212,1041,231,6000,1022,2350,6101,9680,8730,5889,4148,2165,233,9513,5491,5283,9730,3280,5026,671,7910,8109,573,6728,7813,8114,5484,595,5328,9533,4652,3657,1126,2359,3602,9679,1471,1251,6634,9022,4829,3838,6591,8538,602,9744,8062,8248,555,3897,7219,4593,8374,5788,1680,238,7511,3901,650,4058,916,5045,5480,530,7757,5542,4179,7307,7737,6871,1409,4560,2402,9390,9290,305,290,9353,6030,9427,5117,2315,6918,8133,2968,2978,9277,7529,4893,1695,146,464,4733,6649,4127,5030,2156,7083,2333,5475,4439,5032,7036,7203,1364,6660,3523,4288,6006,9736,8469,4852,5013,4732,6202,3257,6315,7479,5899,454,8514,9711,2,2386,561,2430,1581,6098,4527,4012,6894,1835,1012,9108,5123,7162,830,795,778,8252,2192,8972,4508,8070,9267,2364,4191,1570,4949,2892,8711,2064,3801,3510,3434,7670,9856,1904,7765,5808,7590,7561,5863,8137,8519,1359,2051,7471,3493,7618,8759,8713,5691,5191,5864,493,5923,2572,866,5100,3570,8798,7962,7668,5795,2230,5347,7140,2882,5508,9563,6151,9289,2491,1226,1998,8894,6498,4747,7940,6681,8127,7449,1340,5657,2599,7502,4336,5374,7075,6520,4,572,86,8878,2922,2808,7334,8427,2595,7486,8524,4796,6611,6070,1350,7959,1131,1122,6822,6327,4369,6636,658,6173,7782,3046,7042,3645,935,9360,3234,1770,5350,2126,9206,2371,7418,8325,21,6701,6125,7854,3173,1603,4923,7167,298,3026,188,3441,4123,523,9419,9180,3134,6163,6694,1907,1515,832,8625,8281,7060,7326,2507,6526,2897,1587,5937,2110,2125,5391,8527,9346,3239,5587,1229,9485,6575,6846,1858,5170,9425,8827,4353,8350,3813,6957,200,8523,9518,3579,3844,8139,4454,5125,9136,8360,8895,6873,1810,5308,2055,1694,954,7300,7985,8060,3306,9237,1346,2248,3978,7527,9174,5022,6932,12,5928,9770,2632,276,5330,5783,1818,2373,6930,6021,7753,5919,1147,3178,6549,7970,4865,5101,9041,4883,9132,9460,9492,9532,7330,1227,346,2228,5784,7038,8803,4252,3407,1661,1382,3558,80,1374,8485,2568,461,6314,6034,9715,683,273,7823,2783,3682,4635,2196,2955,554,9318,2710,55,5929,5171,1034,6076,6025,6288,6566,2938,8653,5725,8414,475,7283,7612,6975,5294,6388,527,7100,3507,1400,6081,9794,1372,8548,4340,7004,5962,3957,733,1765,6812,2152,6645,6166,3936,3559,2026,4059,8343,2208,9194,260,6666,7935,9910,8996,4365,9671,8231,2227,9545,2684,5476,7180,9163,2131,3650,6450,8181,6531,5986,489,1146,3191,58,9075,5927,1167,5948,4081,592,8767,5301,7293,6486,2270,9217,5645,4615,4867,3543,6981,6332,9596,7973,4758,6213,5346,3141,1836,5239,7025,7029,1306,3123,3896,4718,5575,9632,8471,5590,1232,9183,7934,9665,7936,6781,4221,1912,2754,7085,7768,7621,3629,7556,4871,9173,7090,341,6844,4349,6911,5675,7574,1914,2702,6172,3204,4668,6937,8672,9491,628,9050,4948,6139,8081,498,9600,5955,9436,8690,190,1101,5965,8080,7361,6593,2817,6041,182,311,2444,8048,150,7799,2532,3105,2826,4207,3259,5205,7355,1674,206,7689,7427,8303,5789,8965,6283,9476,421,1371,6652,1894,7194,6882,646,1070,2972,7245,3720,8980,1289,8623,7589,6331,2792,7990,4748,8635,7557,855,6843,5865,904,1922,9087,3562,7260,7217,1297,4713,6556,7846,4955,1185,1733,8902,8706,143,900,8172,6674,3752,6196,9929,2589,3350,8984,7564,8890,3872,3034,6548,9188,8014,4562,6319,4004,9640,1187,54,9682,2477,3021,7178,7697,4171,9271,9478,395,6474,6816,6571,5640,7800,9320,6773,5917,5635,4415,8680,8628,6180,4197,9455,5210,7340,486,910,5868,1166,879,1405,3122,8696,6037,5949,8704,9590,5145,9378,4297,8664,2274,7213,3422,3369,1331,8603,1825,5550,6377,1766,2211,3244,4933,1347,9203,6367,3310,4233,2885,7237,5158,1425,2053,4328,7134,2340,9130,9720,6484,1642,1664,2641,9114,4003,8760,7234,8198,3853,5103,3703,5651,9710,7182,6176,5545,5747,8937,7474,1162,8903,9841,8391,1687,4629,926,3496,9332,9783,5840,3697,3777,2778,4270,9869,9414,2571,3808,8085,515,516,3822,1763,542,2423,8528,7933,8083,3612,8922,9308,4917,5540,612,7711,5877,8744,6581,8850,6338,7998,4111,8963,7458,6574,9700,4962,5068,8578,5398,9064,7929,8401,7831,1170,703,522,6536,5592,7309,7948,8305,2857,8727,1469,3468,8540,6220,1820,9668,4271,6321,5793,7354,253,8957,1917,4130,9191,1991,7324,6236,4399,3158,7780,7572,9017,7020,1688,5289,5561,7043,9065,1419,9739,2526,5820,5106,9254,5207,9033,6414,2195,4140,9364,629,6976,7373,9623,8956,2287,1172,5527,8380,631,6390,8932,8472,7206,6967,7398,889,1285,1618,7841,7646,7332,1902,1718,1492,7851,1493,7403,5235,5722,5812,9508,4195,1768,3290,635,6512,8044,3406,4701,6632,6371,3564,7386,8779,6394,8692,4870,4516,6904,6734,9459,6958,3701,1357,2550,4566,9342,6969,7819,1945,893,8456,7521,532,3208,9354,4006,9453,6922,2677,4343,5632,8940,5149,8931,2362,2427,9129,2521,9839,2401,6663,1100,3809,3791,1483,8050,79,7401,7844,1682,8302,1774,1339,9099,9362,4094,8837,8951,7955,3005,9684,8205,4935,748,9143,9655,9315,2410,8733,642,4925,434,7387,7281,9743,2342,6741,7058,2247,8040,9685,4015,837,5008,2238,4898,5278,6399,301,162,1986,8000,2727,9238,9171,8079,4284,7798,5315,6980,7168,7645,8905,780,6227,328,8566,524,1225,7816,9356,7859,7807,1109,6936,7734,7473,3380,6576,8274,896,4964,3056,8028,4762,8591,1755,5711,8726,8862,8293,9006,9844,7296,2476,6447,2829,4138,8584,9873,1367,9986,6,3929,4255,6862,2912,9264,7313,7562,7094,525,4878,6572,4029,3786,1779,8660,7971,4559,176,7407,7958,2682,5471,5816,8576,897,6813,9486,102,5953,2729,8619,5890,5914,7468,4051,1649,4230,793,1324,8041,4248,7105,4567,657,3873,4420,2864,9543,9909,4786,7096,2825,8659,8562,2170,1,5245,8650,2160,7614,1362,9573,3381,2000,1301,6907,7396,3469,8175,210,8876,8757,6191,9216,4866,3003,3802,6710,1302,6310,1192,5104,7731,865,2873,4863,1494,1551,3109,1954,8488,1819,8255,2089,8246,4805,4277,3082,254,7860,4117,9198,5930,912,1246,9553,9727,562,5281,9061,8958,1264,5320,5662,769,302,6040,5884,7328,3293,7129,4861,100,2609,4459,2079,4524,1069,3916,529,4767,6194,6585,9278,3298,1215,6140,8787,2376,6552,5049,694,5568,9721,8253,718,9477,9101,2289,2573,9324,5911,403,2083,1351,404,2634,7274,3053,3131,2747,175,9931,3803,7537,3029,9051,5833,5776,9098,9811,6590,7263,1552,3869,3394,3542,4260,6155,4707,5243,9923,553,7375,6217,8754,7120,3015,6568,214,5270,9007,6305,9801,192,6902,8087,8223,2172,3048,9877,6673,663,5696,8738,6877,3314,3624,8597,8276,5975,6775,1804,928,2486,825,2007,9365,8554,2369,9902,7759,7316,6430,8883,8484,667,7391,3918,4480,835,1507,6952,1626,1299,8404,437,7597,8016,4798,5705,747,2341,3389,4704,1503,5541,347,2666,7650,6747,878,8613,6341,3393,1941,191,9525,8431,9351,7644,6617,4341,7356,8082,6055,7987,8278,5997,4449,1556,1250,1180,1096,8539,6268,7577,7883,6112,3428,880,7246,3481,514,8437,7704,5589,649,7912,5667,9137,6355,68,2688,1424,5810,4299,1760,6755,4106,7252,3219,3067,2703,5142,1850,2113,4820,9858,9629,939,774,7346,4045,7417,5418,3008,7885,4996,8425,8073,1591,9117,520,9145,5813,5257,1064,677,246,2440,8290,3033,9053,6251,9105,1007,7301,3151,6360,797,2501,9534,1083,5684,5405,2603,7769,9837,5071,2976,4042,6294,4083,5767,3148,6092,4750,2181,216,7928,7223,798,1138,2347,7820,1365,7716,2669,2134,640,4802,2588,4776,9265,7785,7892,5857,5433,990,1557,3986,9257,8388,2276,2948,8,7539,8088,3064,4357,5276,1734,9950,9242,6387,130,5017,4407,9511,1957,4461,5659,5777,9321,5400,3900,9781,2292,6719,3962,9863,4190,2358,3652,2863,3673,9947,5184,9712,999,9406,135,5553,9500,9067,4079,7052,857,8764,533,9222,5983,4918,7877,5701,8443,8122,6874,1106,118,9952,5377,8193,152,7470,9446,3660,1291,3475,7878,8156,1017,339,7310,682,5089,94,6473,318,1746,6783,9693,9372,9291,9109,334,155,13,7909,7685,9387,5501,8879,9160,618,7714,6916,1645,7287,1673,8411,5268,2519,374,7207,9530,3193,7079,6372,2415,1025,1453,9435,3182,3799,5915,5087,9405,596,7701,576,1430,5457,7444,2186,7664,5874,8920,6157,8998,4478,8071,6607,660,1308,6989,7817,124,1588,8571,1928,2874,6250,4315,7687,2534,7982,3540,3045,4761,270,3811,2378,8657,8685,5492,8318,6761,3783,7084,4055,806,6410,451,4389,7747,2116,1615,6152,6620,8728,7788,5063,9741,2329,9753,8891,1712,4435,8196,5894,7559,656,4345,9605,4824,6119,7,2731,2527,1640,2862,5472,9699,8211,9849,1222,7610,83,679,6380,5085,5529,7725,8025,638,5099,1082,3413,6672,108,2590,91,5716,8381,6695,4521,8944,4313,9347,1543,7735,7793,7447,7708,7688,8892,1743,2957,2355,5605,438,6094,8621,321,9875,7457,1303,9402,414,7421,3836,8135,7525,9964,7463,961,5992,2216,1059,8929,1433,1260,1930,4338,5417,8298,1437,1090,8058,6169,7666,7008,4410,7152,154,5474,8461,8913,2799,5878,1720,7161,3327,435,6830,7619,845,1046,4538,2809,3461,8981,1999,3958,6317,1013,5479,3149,5609,9821,6298,5693,7746,3143,1772,9594,4426,6431,2297,9932,8953,3894,7624,6838,3028,9745,9128,9575,6828,3644,7176,2021,4377,9800,7686,7183,2738,5148,3935,43,7498,4146,1438,9737,7348,9654,2970,9542,7485,9819,2597,1269,7993,7719,5412,27,4494,8261,6363,7702,1388,8429,8630,5647,3505,2801,2135,1403,1379,4158,3747,8120,836,5039,5726,2103,9555,4022,9613,7247,8084,2911,4175,6009,8853,5421,156,1670,9528,9190,8370,610,5751,2983,3146,4067,8546,2382,5326,1519,9029,9981,7875,1958,7200,2672,3343,1145,1179,4304,5839,4228,7163,8749,4267,3209,3060,8134,8719,3050,5867,2735,7776,8184,255,462,9069,9587,7158,5014,400,8939,2198,3433,6393,4276,2695,8232,9913,9802,9678,1535,3715,9016,4581,397,2975,8908,763,8919,8794,9982,1500,8095,8752,3806,8508,6292,3668,137,915,2484,5168,6386,5954,6938,8604,7014,9189,3639,5096,3578,6198,766,5850,2448,2918,7059,6368,6373,8658,3591,7103,1060,4932,7349,7509,7141,3705,8230,3945,8926,2174,9692,7254,9400,8620,7279,1386,6901,785,1974,5458,1979,3237,9335,9445,9957,8188,2814,3914,3753,8308,4120,8500,6644,3295,7530,3218,5699,1652,1761,8267,8881,4335,1495,7602,9890,7911,6127,8309,4886,9725,5322,5591,1632,6164,3532,6449,9437,63,1531,8673,4273,3743,1952,4595,9577,6348,9181,7565,2640,1793,962,8573,3361,2220,2497,8289,3457,389,3972,1704,8138,1675,8104,5327,3696,591,319,2706,3092,5375,1949,4702,8019,3917,6561,5886,8997,7137,7790,3646,6396,5386,1862,5926,6881,662,3054,9026,3335,151,9093,4394,5724,2042,4291,4356,3830,7150,7994,3338,6900,4289,864,4529,2636,563,8586,7876,3159,3571,2080,2258,3352,7133,7908,2127,4010,5629,7884,8683,9509,4467,6913,8074,8432,4554,4431,8151,3618,8018,104,9734,3965,4272,8636,9283,5748,4552,3032,2711,6023,560,6580,4254,6760,7956,7694,3494,2514,7703,6534,9854,5424,9948,4565,3616,2638,3778,3328,1532,9576,1722,8395,8333,7035,7431,9895,1043,8841,3932,2052,7045,664,4404,1125,5248,4590,2600,358,8917,8656,9421,9082,7656,7455,2257,2499,1901,2540,3858,3807,7822,2830,3409,6113,7673,1404,8047,8520,643,211,7275,5604,5415,8275,3253,1153,3939,2130,3850,8473,1764,9833,5907,9598,2576,7548,4027,9751,2175,6942,5853,4060,3222,8180,5721,772,203,2368,7109,7238,5307,8992,6998,6274,949,4673,342,5916,8709,5084,9554,6049,9116,5631,5371,3205,6809,3498,5759,4417,4492,220,6994,9865,3952,8999,2365,4145,6477,7099,1081,2927,2683,1273,9812,2314,5020,2411,9581,9608,5903,4132,6029,5097,3365,2947,1745,6088,398,3379,9642,5673,6770,4926,7248,2482,348,1953,3852,3989,2734,7920,6625,8870,3756,4131,2748,7080,2263,8462,641,7861,7399,9997,8491,5176,6748,2421,8468,8684,4305,1710,7906,5547,9411,8479,4588,9852,8357,5909,6277,9273,7478,2784,3566,2583,1005,2887,9527,9380,2147,7752,8024,8108,8561,1050,4212,3959,3594,3710,4331,4972,3640,4568,6602,7739,4261,385,607,8637,9261,4976,1435,9626,7382,4473,2244,9468,8946,1413,6648,3106,1977,7924,8362,5223,2092,1517,4180,6403,8076,5738,7294,9350,1065,9121,3137,5618,2557,1575,7057,3977,9187,9359,430,2488,2635,6405,7233,6923,8858,2601,4203,3734,668,4498,3157,377,5942,9615,7837,2214,9218,9404,519,4385,8206,6577,8600,8820,9961,9348,4496,1749,1824,8889,2900,7842,8483,4799,5648,6851,6598,3292,9582,57,375,9060,4019,2705,4242,9658,8970,1829,1589,7261,565,3614,723,51,7209,40,2308,2041,3611,7295,2870,5465,303,3912,4422,8567,1448,5335,8102,9521,8786,2150,4624,8392,2757,1412,1660,7400,4682,6530,6333,7127,1000,5762,8167,7023,9275,8826,6488,2852,7944,8885,1563,121,2774,1607,839,805,920,1045,2046,5252,2902,549,2284,1234,4398,8197,5131,289,4806,9617,2106,6115,608,1198,274,6740,851,8906,6378,7130,9085,494,6252,767,983,9886,9965,6523,4772,3685,980,1182,7623,2528,1971,4943,3769,5196,2098,9193,3214,5378,8861,2755,8577,8716,7015,9294,7148,1061,8405,1541,1693,7938,5621,1102,9307,2162,2286,8812,4290,2739,6471,8583,3758,5546,4643,1049,2883,6356,9370,9512,3377,8476,6831,3385,2681,938,4740,2305,9259,6745,9853,5293,5504,7115,3997,8654,4656,496,1654,7193,1436,7871,593,4790,7914,7050,6015,3539,6048,2505,7961,4412,8700,998,9652,7543,7830,7392,8581,620,786,9681,3804,2114,8505,2819,1703,4071,2753,9179,8962,4836,8086,8409,386,1716,5354,4005,3585,4294,8144,5922,4813,4036,5095,8497,5881,6130,1446,5847,6060,9025,3526,3551,4895,1473,7595,8481,1133,7504,3275,16,7552,1177,1840,7641,4113,9868,9558,1717,2212,4937,3950,2924,9111,501,589,1860,8282,3683,7499,9774,9466,9834,9732,7041,4397,6758,2796,8166,8460,8416,5288,487,2822,6724,6175,813,7655,1029,6820,2979,8382,4038,1074,4986,4269,8717,1072,6651,6075,4168,7558,8449,1669,5274,361,6200,1252,9897,3454,8218,9302,4152,6465,9493,8249,3522,823,5947,3815,1452,1805,869,7526,2281,1984,4037,588,8928,6413,1796,5517,8681,4626,3238,7086,1874,5905,2316,4095,329,2881,2741,9322,7839,1614,4472,5499,4794,6136,2391,4857,7761,9248,1555,3601,2592,9857,2185,3089,6077,4815,4283,3667,9127,1577,3095,9656,2269,7682,8072,7786,6866,4783,7370,9073,812,7805,52,1771,4170,9921,502,7405,3923,6422,8743,3749,6857,9992,9529,4225,1313,8227,5441,4408,1092,415,2750,84,1186,1699,9541,5712,101,9723,95,5613,4892,6264,3708,8941,659,9288,3949,913,794,8529,4077,4482,3774,9336,760,8753,2203,7078,8131,285,8874,5234,8345,1657,7380,3500,1644,3788,7900,4657,5566,9286,5576,234,7953,8670,9081,3741,1316,7345,440,3525,9881,7460,1613,2136,5292,8068,1310,6856,698,9309,8224,5473,189,9523,5772,2728,9804,3453,2387,7191,6776,7902,4605,5960,5195,2419,243,6716,3733,6454,8674,153,5389,416,8148,4915,773,8408,8925,1158,4136,1151,5577,4736,8238,8772,2142,4603,6149,6835,76,5209,1026,8421,5694,7136,1497,1510,2426,4105,3516,9933,5163,4061,9989,4571,3980,9646,453,1163,3269,2251,8732,2845,8455,6544,8376,1608,3016,5323,6005,9818,1298,1573,3721,5633,3483,6145,9904,6807,8202,1807,8721,251,3971,8843,304,6985,6693,6987,8780,6791,8039,3976,810,7484,5688,9244,3161,2984,1512,1253,1758,2442,5373,2190,3118,870,6395,8665,1416,5775,2868,8679,9358,7932,7422,8438,6887,3355,7424,2233,4178,3572,8011,1210,5075,9030,8814,349,4406,7918,2438,5970,8396,9004,9694,720,6044,9972,4927,8182,8633,4074,6991,9200,8199,4900,3037,7862,1653,6949,439,924,4525,8457,9915,9621,652,8912,4466,179,6171,2478,3023,3831,940,1844,557,9412,7235,3940,6409,2124,9559,5978,8642,4163,9911,3860,9696,3704,9049,3119,9469,5468,2977,619,9106,394,9828,3270,7303,3973,2719,8769,6699,4392,4818,7451,5572,4174,1837,611,1143,1714,7098,692,5778,4124,8530,4448,6135,4121,8183,9046,9522,2660,5287,1407,2520,2492,8955,6342,8489,5707,3765,8051,1478,521,8796,9807,909,4899,8952,6188,7022,5428,8888,4511,4268,623,7580,3761,2626,8038,6466,8020,8428,9847,7010,5862,5275,6633,8865,7531,7549,6437,2029,8593,6275,3695,8560,9133,507,3304,8154,6329,9119,5977,1854,3992,1853,6482,1893,4122,7481,8214,2398,8155,508,1272,6099,5219,239,3982,2337,1594,2153,1477,5805,116,4213,491,8002,8327,5757,6765,6910,6408,5496,8773,6759,9566,3435,2034,4726,819,8678,7071,1609,3210,3114,7121,9722,4181,3528,1987,333,2585,2437,8933,5438,9785,6546,8335,6555,7927,1021,8596,6452,9112,5557,353,9601,3154,7999,9483,5556,9568,1549,8697,444,1075,3093,3307,5834,7632,6248,6064,8373,7814,4423,3956,7339,8171,6785,5113,3264,1678,2559,2097,9166,8492,736,5842,9076,2243,7202,5313,6126,2515,2464,8149,3553,3508,569,1502,5119,586,6184,8091,4460,5520,9862,994,1129,1480,2223,4826,2121,6766,7311,3302,8226,4753,2177,1646,8629,4724,8037,8624,9633,3796,1066,2472,8893,9266,2541,9823,2450,3750,9152,1871,4052,8130,3229,4361,338,1845,5646,8810,4513,9256,7905,1327,288,7435,8406,4620,7791,1047,5829,3689,3041,2171,2232,4780,925,7847,3506,9867,577,3941,169,8745,8974,6706,458,686,5579,4561,9829,2163,312,731,4743,4587,5597,3881,3677,3798,5144,2974,9339,287,1052,9660,7547,3402,9150,1748,3548,9343,9547,5352,366,5800,2854,3870,8096,71,6921,5584,5411,8331,4644,1962,4942,1697,2551,4703,6687,9822,6623,6230,908,5814,1334,5674,2404,5203,7426,3590,2723,4654,167,853,4931,9899,3748,9706,9207,4188,8936,2433,3172,8356,2063,6193,6071,2574,8115,1841,1681,6492,6817,1861,8979,1396,2954,293,8067,9349,1920,9714,8316,6943,1095,9424,4541,8017,8200,4543,9985,1630,7872,3192,8525,2095,6002,6128,2462,1511,6829,8807,5172,1631,4647,8033,3920,2952,4296,5826,3458,761,695,1857,1924,307,2544,6154,3401,9475,714,5995,2932,3099,2508,3043,1859,1120,3938,7276,5363,8518,2236,7264,9718,4323,8394,8995,1877,2899,1408,9361,9301,5876,9442,4184,2299,9367,4086,9223,283,1738,4928,5622,5513,5187,3567,5835,5376,9276,3762,2167,1463,3610,5487,3360,6601,1927,9836,7067,265,3383,5197,5329,5854,8247,109,8045,3693,5560,6692,5898,8031,1098,5936,250,2524,8153,3010,3623,6019,6285,5188,9966,412,2091,6933,1112,4032,2580,292,4868,4275,2229,8300,3530,127,1111,7613,1891,4622,1568,9062,8498,2593,5582,5192,9631,7639,4250,1735,1576,5178,2928,7117,5563,2937,8030,5345,8495,2543,4018,8712,8494,9423,9726,5384,3286,8244,6560,8420,8557,9611,6650,4039,503,2200,9674,923,2907,5259,1655,8734,2002,7635,4342,6424,903,9458,6613,1890,9385,158,7755,9591,1239,3819,2259,9089,8927,66,9299,4658,6510,5297,5961,5037,4755,5074,9255,4295,8901,1578,4144,139,1067,5797,5639,9795,5455,9124,5285,4057,7942,4557,546,7107,2740,8240,707,9045,7648,1536,1611,4068,9792,5261,6720,1496,9552,944,7792,2876,6562,2129,4708,9567,9115,9462,9892,423,5567,112,9311,4641,8677,6468,8646,3324,5624,1621,9241,9376,6594,3436,3279,9373,4746,9449,271,2525,9147,4676,3387,7651,6527,431,5717,9956,4487,1104,8766,2237,7691,5968,4142,613,5729,6334,9928,1792,5070,4844,1639,9724,4885,9763,5799,7626,3638,4709,7835,697,4194,8053,5531,4522,987,2056,6926,2651,313,5934,9472,5088,1376,3871,814,979,3839,2424,6109,266,4374,8475,3201,4279,4322,7787,9638,8179,8782,7566,3975,9784,1114,2154,7964,4438,2311,3190,370,8399,2432,5393,4533,6567,1961,8555,4048,4825,2732,8105,2100,8194,3039,3116,3375,5973,9015,7681,9850,1117,7388,6973,1967,3164,7767,8521,205,9979,1908,3759,2396,6712,2239,4782,8966,368,2708,3024,9719,1946,7177,4642,7037,2068,5892,1997,5935,3864,1947,5515,309,2994,3538,5532,2058,6400,235,8236,2496,6667,7824,7104,9473,449,3883,5365,2771,9296,6743,1856,9662,8057,5135,1643,2960,8239,675,4224,6855,9589,6514,5708,5076,4532,2958,4691,2118,3419,3678,9908,1020,5369,1726,3291,184,7960,4329,9756,8503,1547,4364,4320,2909,3185,8441,1787,7796,4321,6354,5664,3903,6631,1641,4054,9733,2843,3297,5951,1431,161,6570,8078,5153,7951,9184,3415,548,2019,1454,6731,6018,3942,8424,5152,8066,7255,7706,4418,4773,2025,7317,3779,712,1084,5537,6700,4874,9766,969,3051,5663,9891,6322,3487,330,3846,2671,2889,3285,5035,8169,9157,8627,7006,9624,6619,6123,1168,9037,2859,3833,5824,7996,5642,3817,899,2399,2998,8616,1441,262,286,689,481,5456,559,9233,5521,3995,3581,1476,5280,1848,5200,252,7253,8052,7262,6345,6515,4922,5982,3563,7377,9043,8266,6263,9735,1834,2470,75,4645,5588,3245,2366,1202,8762,3127,325,427,9980,8093,4333,3320,3556,9954,7809,8386,6022,8834,4362,1869,5525,8174,160,4683,7889,9330,1048,8023,9888,4804,9772,1154,2717,5610,8724,3390,883,426,3430,5416,8802,5720,7541,6222,3358,136,1913,1606,4161,2360,9705,8251,9389,9546,8647,6524,5263,802,9515,9068,6883,4599,2306,3135,8297,1872,5331,7897,3049,968,9941,741,8682,1213,8522,1795,6858,5048,4078,7896,381,1343,9748,380,8868,1803,6312,4837,8605,7154,4453,5770,8804,3305,5009,1659,1663,48,9395,9860,418,5453,22,8968,4245,9021,5062,5442,7119,713,8400,2189,6668,8614,9943,2219,7185,8049,3455,950,9209,3142,5999,6042,970,4845,9973,5007,891,6836,4694,3451,7815,93,3985,7171,8849,8991,7297,384,9672,5404,5208,6614,5156,5132,2271,8322,706,1300,5181,9782,1391,6300,3288,2775,1220,4954,6665,5338,6895,4489,3729,3315,8545,9709,9178,5523,2617,6819,3549,3501,2908,8739,7282,8344,6084,6796,7074,4293,1802,3240,7894,5226,6790,3236,1822,4914,2562,4872,4159,4436,4160,1010,4611,651,7647,2144,8987,7259,8898,8731,7369,9990,465,327,7843,3497,2405,5316,8553,8911,8564,7027,722,3954,2657,6708,7395,9901,3603,7439,7513,8348,5714,1888,842,4634,1194,974,936,9249,3088,594,4064,6398,3014,6736,3284,5786,4303,3258,1121,8788,5175,6702,4133,5872,3670,9959,824,5683,6072,6897,6369,3658,8165,9422,8090,9167,8818,7575,73,8383,582,624,8515,7005,942,7870,1255,1866,9001,3767,1729,6490,8626,9675,8217,9683,7404,7166,5290,1123,9122,3641,6318,4414,8971,7327,2765,4035,3550,7555,7146,7950,5004,4166,4830,297,1199,2553,6977,9851,2856,4792,9574,8005,7214,5620,9426,7184,60,9765,467,5216,1937,5637,7880,6261,9644,6637,4610,3000,7611,9205,9253,8784,1769,9776,2965,6432,4697,7196,8285,1200,8918,4393,7508,955,5904,9176,4154,2914,1188,7637,6379,3140,9687,3967,9186,9816,1261,3465,4851,5801,8662,3124,7409,9627,3632,2866,9764,9651,3040,598,5446,7208,6635,7110,2622,7741,1969,2618,6795,7573,2851,3129,3554,7144,6385,5871,3544,2168,4173,9805,6131,1719,5396,764,4862,8921,1916,4960,7802,550,5933,2009,8720,4693,2313,4434,4308,982,9168,6553,9495,5569,5737,9285,1468,4788,3821,5266,3636,7333,6079,9667,735,5785,7965,9161,6538,141,9820,9282,9328,9501,8077,945,3706,473,687,6309,4209,2602,5773,6806,2145,9759,7363,5470,410,6996,131,4354,5082,3648,3647,1982,1994,3655,9755,6204,6750,8342,6053,539,7500,3740,1993,7867,4819,9140,111,4583,5213,1981,745,826,2096,6209,7981,2556,9177,4897,9650,9023,9717,8705,2578,9838,886,7717,9272,4310,7840,9228,1604,2921,2764,4988,8355,9670,1011,9762,9777,4118,9606,6805,1245,7002,7519,8954,1559,1243,9415,2403,9729,9752,177,8069,8161,8758,8056,5019,4090,9279,8735,1602,2011,9019,2849,6284,133,8829,3635,3443,5650,1529,4509,7480,9428,7775,1062,538,5133,1212,3944,3438,9944,5146,6392,8147,3260,3038,8454,1964,2837,7629,5129,2146,5122,1900,5325,7402,7758,4621,6096,575,783,9887,2003,4613,7874,3345,6542,4499,9939,9550,344,3866,3200,9396,1899,4757,8989,3351,8543,8234,8324,2288,6097,4765,6717,6311,7365,5107,9861,6940,3847,212,6228,2392,7054,1851,6352,2326,9536,4474,3065,1617,1545,7442,9355,3152,2016,6122,7764,5670,1110,3726,2880,9369,4443,7931,2179,3592,3163,8435,3079,3754,852,4572,4488,2680,2105,8934,2894,5866,1418,9319,7957,7593,9639,6948,7789,8284,981,7907,2890,3011,8306,6443,2565,3477,185,3179,4222,2254,2776,5601,2111,7712,4097,3102,376,6073,3764,300,8570,1852,1799,9927,140,9304,665,9071,9399,9708,6529,4030,8882,7420,6301,1282,8916,9914,2566,9622,4575,2414,4241,2356,1711,4617,9368,3031,7915,932,6247,7197,2469,6435,142,1809,9104,2944,9314,6810,4721,3993,2225,2502,7569,5906,9922,77,4240,2661,4763,2509,6852,9855,9831,3384,890,3878,4253,4977,4859,6686,6273,7072,7699,6121,1094,7108,7653,36,807,49,1580,1911,1294,7081,4536,8569,1332,6106,4966,9393,7179,4235,2073,2761,5137,280,1702,9052,4165,934,7383,2357,8477,3363,3215,2417,8099,7204,1833,2182,4244,4768,5064,1620,4653,8258,8611,7320,9149,4578,5343,6457,8791,229,8203,5300,4811,8559,7218,6160,8589,5318,3242,4616,3318,7620,1561,4771,6705,1440,5214,816,8106,7364,3782,7188,8003,9482,9054,1283,5740,9490,6067,8640,7266,5792,9269};
	}			 
	

	private void sort(int[] a, int l, int r) {
		int p;

		if (l < r) {
			totalComparisons +=r-l;
			
			p = partion(a, l, r);
			sort(a, l, p - 1);
			sort(a, p + 1, r);
		}
	}

	private int partion(int[] a, int l, int r) {
		
		int median = medianOf3(a, l, r);
		exchange(a, l, median);
		
		int pivot = a[l];
		int i = l + 1;
		for (int j = l + 1; j <= r; j++) {
			if (a[j] < pivot) {
				exchange(a, i, j);
				i++;
			}
		}
		exchange(a, l, i - 1);
		return i - 1;
	}

	private static void exchange(int[] a, int m, int n) {
		int temp = a[m];
		a[m] = a[n];
		a[n] = temp;
	}

	
	private static int medianOf3(int[] a,int l, int r) {
		int center = (l+r)/2;
		if      ( (a[r] <= a[center] && a[center] <= a[l]) || (a[r] >= a[center] && a[center] >= a[l]) )
			return center;
		else if ( (a[center] <= a[r] && a[r] <= a[l]) || (a[center] >= a[r] && a[r] >= a[l]) )
			return r;
		else  if( (a[center] <= a[l] && a[l] <= a[r]) || (a[center] >= a[l] && a[l] >= a[r]) )
			return  l;
		else 
			return -1;
		}
}
